{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Stone Game IX"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #math #counting #game-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #数学 #计数 #博弈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: stoneGameIX"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #石子游戏 IX"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子，每个石子都有一个关联的数字表示它的价值。给你一个整数数组 <code>stones</code> ，其中 <code>stones[i]</code> 是第 <code>i</code> 个石子的价值。</p>\n",
    "\n",
    "<p>Alice 和 Bob 轮流进行自己的回合，<strong>Alice</strong> 先手。每一回合，玩家需要从 <code>stones</code>&nbsp;中移除任一石子。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果玩家移除石子后，导致 <strong>所有已移除石子</strong> 的价值&nbsp;<strong>总和</strong> 可以被 3 整除，那么该玩家就 <strong>输掉游戏</strong> 。</li>\n",
    "\t<li>如果不满足上一条，且移除后没有任何剩余的石子，那么 Bob 将会直接获胜（即便是在 Alice 的回合）。</li>\n",
    "</ul>\n",
    "\n",
    "<p>假设两位玩家均采用&nbsp;<strong>最佳</strong> 决策。如果 Alice 获胜，返回 <code>true</code> ；如果 Bob 获胜，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>stones = [2,1]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>游戏进行如下：\n",
    "- 回合 1：Alice 可以移除任意一个石子。\n",
    "- 回合 2：Bob 移除剩下的石子。 \n",
    "已移除的石子的值总和为 1 + 2 = 3 且可以被 3 整除。因此，Bob 输，Alice 获胜。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>stones = [2]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>Alice 会移除唯一一个石子，已移除石子的值总和为 2 。 \n",
    "由于所有石子都已移除，且值总和无法被 3 整除，Bob 获胜。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>stones = [5,1,2,4,3]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>Bob 总会获胜。其中一种可能的游戏进行方式如下：\n",
    "- 回合 1：Alice 可以移除值为 1 的第 2 个石子。已移除石子值总和为 1 。\n",
    "- 回合 2：Bob 可以移除值为 3 的第 5 个石子。已移除石子值总和为 = 1 + 3 = 4 。\n",
    "- 回合 3：Alices 可以移除值为 4 的第 4 个石子。已移除石子值总和为 = 1 + 3 + 4 = 8 。\n",
    "- 回合 4：Bob 可以移除值为 2 的第 3 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 = 10.\n",
    "- 回合 5：Alice 可以移除值为 5 的第 1 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 + 5 = 15.\n",
    "Alice 输掉游戏，因为已移除石子值总和（15）可以被 3 整除，Bob 获胜。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= stones.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= stones[i] &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [stone-game-ix](https://leetcode.cn/problems/stone-game-ix/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [stone-game-ix](https://leetcode.cn/problems/stone-game-ix/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1]', '[2]', '[5,1,2,4,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        # 1 1 2 1 2 1 2 1 2 ...\n",
    "        # 2 2 1 2 1 2 1 2 1 ...\n",
    "        cnts = [0] * 3\n",
    "        for num in stones:\n",
    "            if not (m := num % 3):\n",
    "                cnts[m] ^= 1\n",
    "            else:\n",
    "                cnts[m] += 1\n",
    "        if not cnts[0]:\n",
    "            # Alice获胜的策略必然是先取1或2中更少的那个，如果有一个没得可取，\n",
    "            # 那么Alice必然是拿到第一个模3余0（第三次为Alice取），要么石子全拿光也不会是0（比如两个1）\n",
    "            return min(cnts[1], cnts[2]) > 0\n",
    "        else:\n",
    "            # 拥有了一个先手反制的选择（再非第一回合选择模3余0的数，会导致本来该自己必须选某堆石子变为对方必须先选）\n",
    "            # 那么Alice第一回合必须拿更多的那边的石子（更少会导致对方拿模3余0，我们面对上面分析的必输态）\n",
    "            # 如果拿走一个以后，更多的石子和另一堆一样多 或者 只多一个，那么Bob总有永远和不为3且取光所有石子的选择。\n",
    "            return abs(cnts[1] - cnts[2]) > 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        cnt = [0] * 3\n",
    "        for v in stones:\n",
    "            cnt[v % 3] += 1\n",
    "        if cnt[0] % 2 == 0 and cnt[1] * cnt[2] > 0:\n",
    "            return True\n",
    "        if cnt[0] % 2 == 1 and abs(cnt[1] - cnt[2]) >= 3:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        cnt0 = cnt1 = cnt2 = 0\n",
    "        for val in stones:\n",
    "            if (typ := val % 3) == 0:\n",
    "                cnt0 += 1\n",
    "            elif typ == 1:\n",
    "                cnt1 += 1\n",
    "            else:\n",
    "                cnt2 += 1\n",
    "        if cnt0 % 2 == 0:\n",
    "            return cnt1 >= 1 and cnt2 >= 1\n",
    "        return cnt1 - cnt2 > 2 or cnt2 - cnt1 > 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        cnt = [0] * 3\n",
    "        for v in stones:\n",
    "            cnt[v % 3] += 1\n",
    "        if cnt[0] % 2 == 0 and cnt[1] * cnt[2] > 0:\n",
    "            return True\n",
    "        if cnt[0] % 2 == 1 and abs(cnt[1] - cnt[2]) >= 3:\n",
    "            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        b = [0] * 3\n",
    "        for s in stones:\n",
    "            b[s % 3] += 1\n",
    "\n",
    "        def check(i):\n",
    "            a = deepcopy(b)\n",
    "            a[i] -= 1\n",
    "            cnt = i\n",
    "            n = len(stones) - 1\n",
    "            turn = 1\n",
    "            while n > 0:\n",
    "                if a[0] > 0:\n",
    "                    a[0] -= 1\n",
    "                elif a[cnt] > 0:\n",
    "                    a[cnt] -= 1\n",
    "                    cnt = 3 - cnt\n",
    "                else:\n",
    "                    return bool(turn)\n",
    "                n -= 1\n",
    "                turn = 1 - turn\n",
    "            return False\n",
    "        \n",
    "        if b[1] > 0 and check(1): return True\n",
    "        if b[2] > 0 and check(2): return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        s = [0,0,0]\n",
    "        for i in stones:\n",
    "            s[i % 3] += 1\n",
    "        if s[1] * s[2] > 0 and s[0] % 2 == 0:\n",
    "            return True\n",
    "        elif abs(s[1] - s[2]) >= 3 and s[0]%2 == 1:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        count=[0,0,0]\n",
    "        for stone in stones:\n",
    "            count[stone%3]+=1\n",
    "        if (count[1]==0 and count[2]<3) or (count[1]<3 and count[2]==0):\n",
    "            return False\n",
    "        if count[1]==0 or count[2]==0:\n",
    "            return (count[0]&1)!=0\n",
    "        if (count[0]&1)==0:\n",
    "            return True\n",
    "        return abs(count[1]-count[2])>2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        counts = [0, 0, 0]\n",
    "        for stone in stones:\n",
    "            counts[stone % 3] += 1\n",
    "        if counts[0] % 2 == 0:\n",
    "            return counts[1] >= 1 and counts[2] >= 1\n",
    "        else:\n",
    "            return abs(counts[1] - counts[2]) > 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        zero = one = two = 0\n",
    "        for stone in stones:\n",
    "            if stone % 3 == 0:\n",
    "                zero += 1\n",
    "            elif stone % 3 == 1:\n",
    "                one += 1\n",
    "            else:\n",
    "                two += 1\n",
    "\n",
    "        ma, mi = one, two\n",
    "        if ma < mi:\n",
    "            ma, mi = mi, ma\n",
    "        \n",
    "        if mi == 0:\n",
    "            return ma > 2 and zero % 2 == 1\n",
    "        \n",
    "        if zero % 2 == 0:\n",
    "            return True\n",
    "\n",
    "        return ma - mi > 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        count = [0, 0, 0]\n",
    "        for stone in stones:\n",
    "            count[stone % 3] += 1\n",
    "\n",
    "        if count[1] == 0 and count[2] == 0:\n",
    "            return False\n",
    "        if count[0] % 2 == 0:\n",
    "            return count[1] > 0 and count[2] > 0\n",
    "        else:\n",
    "            return abs(count[1] - count[2]) > 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        cnt = [0,0,0]\n",
    "        for v in stones: cnt[v%3] += 1\n",
    "        if cnt[0]%2==0:return cnt[1] >=1 and cnt[2]>=1\n",
    "        return abs(cnt[1]-cnt[2])>2\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        n = len(stones)\n",
    "        if n == 1: return False\n",
    "        \n",
    "        def check(first, mod):\n",
    "            if mod[first] > 0:\n",
    "                mod[first] -= 1\n",
    "                state = first\n",
    "                while True:\n",
    "                    # bob\n",
    "                    if mod[state] > 0: \n",
    "                        mod[state] -= 1\n",
    "                        state = 3 - state\n",
    "                    elif mod[0] > 0:\n",
    "                        mod[0] -= 1\n",
    "                    else:\n",
    "                        return True\n",
    "                    \n",
    "                    if mod[0] + mod[1] + mod[2] == 0:\n",
    "                        return False\n",
    "                    \n",
    "                    # alice\n",
    "                    if mod[state] > 0: \n",
    "                        mod[state] -= 1\n",
    "                        state = 3 - state\n",
    "                    elif mod[0] > 0:\n",
    "                        mod[0] -= 1\n",
    "                    else:\n",
    "                        return False\n",
    "                    \n",
    "                    if mod[0] + mod[1] + mod[2] == 0:\n",
    "                        return False\n",
    "            \n",
    "            return False\n",
    "        \n",
    "        mods = [0, 0, 0]\n",
    "        for i in range(n):\n",
    "            mods[stones[i] % 3] += 1\n",
    "            \n",
    "        # alice第一步只能取1或者2\n",
    "        return check(1, mods[:]) or check(2, mods[:])\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        arr = [0,0,0]\n",
    "        for s in stones:\n",
    "            arr[s%3]+=1\n",
    "\n",
    "        def f(cnt):\n",
    "            if cnt[1]==0:\n",
    "                return False\n",
    "            cnt[1]-=1\n",
    "            turns = 1 + cnt[0] + min(cnt[1],cnt[2])*2\n",
    "            \n",
    "            if cnt[1] > cnt[2]:\n",
    "                turns += 1\n",
    "                cnt[1] -=1\n",
    "        \n",
    "            return turns % 2 == 1 and cnt[1] != cnt[2]\n",
    "        return f(arr.copy()) or f([arr[0],arr[2],arr[1]])\n",
    "                \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        n = len(stones)\n",
    "        rec = [0]*3\n",
    "        for s in stones:\n",
    "            rec[s%3]+=1\n",
    "        res = False\n",
    "        #先拿1\n",
    "        s0,s1,s2 = rec[0],rec[1],rec[2]\n",
    "        if s1>0:\n",
    "            cot = 1+2*min(s1-1, s2)+s0+(1 if s1-1>s2 else 0)\n",
    "            if cot%2==1 and cot<n:\n",
    "                res = True\n",
    "        if s2>0:\n",
    "            cot = 1+2*min(s1, s2-1)+s0+(1 if s2-1>s1 else 0)\n",
    "            if cot%2==1 and cot<n:\n",
    "                res = True\n",
    "        #先拿2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        cnts = [0] * 3\n",
    "        for num in stones:\n",
    "            if not (m := num % 3):\n",
    "                cnts[m] ^= 1\n",
    "            else:\n",
    "                cnts[m] += 1\n",
    "        if not cnts[0]:\n",
    "            return min(cnts[1], cnts[2]) > 0\n",
    "        else:\n",
    "            return abs(cnts[1] - cnts[2]) > 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        cnt = [0] * 3\n",
    "        for i in stones:\n",
    "            cnt[i % 3] += 1\n",
    "        if cnt[0] % 2 == 0 and cnt[1] * cnt[2] > 0:\n",
    "            return True\n",
    "        if cnt[0] % 2 == 1 and abs(cnt[1] - cnt[2]) >= 3:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        # 随机移除一个数字 将某个局面留给你\n",
    "        # 最后的结果就是剩下1 还是剩下2\n",
    "        def check(c):\n",
    "            # 第一回合选择1 还是选择2\n",
    "            al = sum(c)\n",
    "            if c[1] == 0:\n",
    "                return False\n",
    "            c[1] -= 1\n",
    "            # 交替选择1或者2\n",
    "            turn = 1 + min(c[1], c[2]) * 2 + c[0]\n",
    "            if c[1] > c[2]:\n",
    "                turn += 1\n",
    "                c[1] -= 1\n",
    "            return turn % 2 == 1 and turn != al\n",
    "        cnt = [0, 0, 0]\n",
    "        for i in stones:\n",
    "            cnt[i%3] += 1\n",
    "        # alice第一次先手选择1 还是先手选择2\n",
    "        # 1 2 指的是使得和余数为1 还是2 的办法 有一种能让alice赢即可\n",
    "        return check(cnt.copy()) or check([cnt[0], cnt[2], cnt[1]])\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        n = len(stones)\n",
    "        rec = [0]*3\n",
    "        for s in stones:\n",
    "            rec[s%3]+=1\n",
    "        res = False\n",
    "        #先拿1\n",
    "        s0,s1,s2 = rec[0],rec[1],rec[2]\n",
    "        if s1>0:\n",
    "            cot = 1+2*min(s1-1, s2)+s0+(1 if s1-1>s2 else 0)\n",
    "            if cot%2==1 and cot<n:\n",
    "                res = True\n",
    "        #先拿2\n",
    "        if s2>0:\n",
    "            cot = 1+2*min(s1, s2-1)+s0+(1 if s2-1>s1 else 0)\n",
    "            if cot%2==1 and cot<n:\n",
    "                res = True\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        def check(c:List[int]):\n",
    "            if c[1]==0:\n",
    "                return False\n",
    "            c[1]-=1\n",
    "            turn=1+min(c[1],c[2])*2+c[0]\n",
    "            if c[1]>c[2]:\n",
    "                turn+=1\n",
    "                c[1]-=1\n",
    "            return turn%2==1 and c[1]!=c[2]\n",
    "        c=[0]*3\n",
    "        for stone in stones:\n",
    "            c[stone%3]+=1\n",
    "        c1=[c[0],c[2],c[1]]\n",
    "        return check(c) or check(c1)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        # 分类构造，cnt0/cnt1/cnt2 分别表示石子值%3=0/1/2的个数\n",
    "        cnt0 = cnt1 = cnt2 = 0\n",
    "        for val in stones:\n",
    "            if (typ := val % 3) == 0:\n",
    "                cnt0 += 1\n",
    "            elif typ == 1:\n",
    "                cnt1 += 1\n",
    "            else:\n",
    "                cnt2 += 1\n",
    "        if cnt0 % 2 == 0:\n",
    "            return cnt1 >= 1 and cnt2 >= 1\n",
    "        return cnt1 - cnt2 > 2 or cnt2 - cnt1 > 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        cnts = [0] * 3\n",
    "        for num in stones:\n",
    "            if not (m := num % 3):\n",
    "                cnts[m] ^= 1\n",
    "            else:\n",
    "                cnts[m] += 1\n",
    "        if not cnts[0]:\n",
    "            return min(cnts[1], cnts[2]) > 0\n",
    "        else:\n",
    "            return abs(cnts[1] - cnts[2]) > 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        cnt = Counter()\n",
    "        for s in stones:\n",
    "            cnt[s % 3] += 1\n",
    "        \n",
    "        a, b, c = cnt[1], cnt[2], cnt[0]\n",
    "\n",
    "        if c % 2 == 0:\n",
    "            if a == 0 or b == 0:\n",
    "                return False\n",
    "        else:\n",
    "            if abs(a - b) <= 2:\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        # 随机移除一个数字 将某个局面留给你\n",
    "        # 最后的结果就是剩下1 还是剩下2\n",
    "        def check(c):\n",
    "            # 第一回合选择1 还是选择2\n",
    "            if c[1] == 0:\n",
    "                return False\n",
    "            c[1] -= 1\n",
    "            # 交替选择1或者2\n",
    "            turn = 1 + min(c[1], c[2]) * 2 + c[0]\n",
    "            if c[1] > c[2]:\n",
    "                turn += 1\n",
    "                c[1] -= 1\n",
    "            return turn % 2 == 1 and c[1] != c[2]\n",
    "        cnt = [0, 0, 0]\n",
    "        for i in stones:\n",
    "            cnt[i%3] += 1\n",
    "        # alice第一次先手选择1 还是先手选择2\n",
    "        # 1 2 指的是使得和余数为1 还是2 的办法 有一种能让alice赢即可\n",
    "        return check(cnt.copy()) or check([cnt[0], cnt[2], cnt[1]])\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        # 随机移除一个数字 将某个局面留给你\n",
    "        # 最后的结果就是剩下1 还是剩下2\n",
    "        al = len(stones)\n",
    "        def check(c):\n",
    "            # 第一回合选择1 还是选择2\n",
    "            if c[1] == 0:\n",
    "                return False\n",
    "            c[1] -= 1\n",
    "            # 交替选择1或者2\n",
    "            turn = 1 + min(c[1], c[2]) * 2 + c[0]\n",
    "            if c[1] > c[2]:\n",
    "                turn += 1\n",
    "                c[1] -= 1\n",
    "            # 轮到bob选石头 而且还有剩余石头 这个时候剩下的石头肯定是使得和的余数是3的\n",
    "            return turn % 2 == 1 and turn != al\n",
    "        cnt = [0, 0, 0]\n",
    "        for i in stones:\n",
    "            cnt[i%3] += 1\n",
    "        # alice第一次先手选择1 还是先手选择2\n",
    "        # 1 2 指的是使得和余数为1 还是2 的办法 有一种能让alice赢即可\n",
    "        return check(cnt.copy()) or check([cnt[0], cnt[2], cnt[1]])\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        stones = [x % 3 for x in stones]\n",
    "        n = len(stones)\n",
    "        counter = Counter(stones)\n",
    "        if counter[1] == counter[2] == 0:\n",
    "            return False\n",
    "        if counter[1] == 0:\n",
    "            # 2 最多用两次，其他都用 0\n",
    "            t = min(2, counter[2]) + counter[0]\n",
    "            return True if t & 1 and t != n else False\n",
    "        if counter[2] == 0:\n",
    "            # 1 最多用两次，其他都用 0\n",
    "            t = min(2, counter[1]) + counter[0]\n",
    "            return True if t & 1 and t != n else False\n",
    "        # 先走1\n",
    "        x1 = min(counter[1] - 1, counter[2])\n",
    "        t1 = 1 + x1 * 2 + (counter[1] - 1 > x1) + counter[0]  # 一共能走的步数\n",
    "        # 先走2\n",
    "        x2 = min(counter[2] - 1, counter[1])\n",
    "        t2 = 1 + x2 * 2 + (counter[2] - 1 > x2) + counter[0]  # 一共能走的步数\n",
    "        if (t1 & 1 and t1 != n) or (t2 & 1 and t2 != n):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        cnt = Counter([x%3 for x in stones])\n",
    "        return abs(cnt[1]-cnt[2])>2 if cnt[0] & 1 else min(cnt[1],cnt[2])>0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        cnt = Counter([x%3 for x in stones])\n",
    "        return abs(cnt[1]-cnt[2])>2 if cnt[0] & 1 else min(cnt[1],cnt[2])>0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        cnt = Counter([x%3 for x in stones])\n",
    "        return abs(cnt[1]-cnt[2])>2 if cnt[0] & 1 else min(cnt[1],cnt[2])>0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        cnt = Counter([x%3 for x in stones])\n",
    "        return abs(cnt[1]-cnt[2])>2 if cnt[0] & 1 else min(cnt[1],cnt[2])>0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def stoneGameIX(self, stones: List[int]) -> bool:\n",
    "        stones = [stone % 3 for stone in stones]\n",
    "        cnts = Counter(stones)\n",
    "\n",
    "        def dfs(cnts,x,i):\n",
    "            if x == 1:\n",
    "                if cnts[1] > 0:\n",
    "                    cnts[1] -= 1\n",
    "                    if dfs(cnts,2,(i+1)%2):\n",
    "                        return True\n",
    "                    cnts[1] += 1\n",
    "                if cnts[0] % 2 == 0:\n",
    "                    return True if cnts[2] != 0 and cnts[1] == 0 and i % 2 == 1 else False\n",
    "                return True if cnts[2] != 0 and cnts[1] == 0 and i % 2 == 0 else False\n",
    "            elif x == 2:\n",
    "                if cnts[2] > 0:\n",
    "                    cnts[2] -= 1\n",
    "                    if dfs(cnts,1,(i+1)%2):\n",
    "                        return True\n",
    "                    cnts[2] += 1\n",
    "                if cnts[0] % 2 == 0:\n",
    "                    return True if cnts[1] != 0 and cnts[2] == 0 and i % 2 == 1 else False\n",
    "                return True if cnts[1] != 0 and cnts[2] == 0 and i % 2 == 0 else False\n",
    "            else:\n",
    "                if cnts[1] > 0:\n",
    "                    cnts[1] -= 1\n",
    "                    if dfs(cnts,1,(i+1)%2):\n",
    "                        return True\n",
    "                    cnts[1] += 1\n",
    "                if cnts[2] > 0:\n",
    "                    cnts[2] -= 1\n",
    "                    if dfs(cnts,2,(i+1)%2):\n",
    "                        return True\n",
    "                    cnts[2] += 1\n",
    "                return True if cnts[0] > 0 and cnts[1] == 0 and cnts[2] == 0 and i % 2 == 1 else False\n",
    "\n",
    "        return dfs(cnts,0,0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
